{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3bd93cf8",
   "metadata": {},
   "source": [
    "常见三种任务：\n",
    "* 回归问题：是预测一个连续的数值，例如明天降雨量，股票涨跌幅度等等；\n",
    "* 分类问题：预测猫、狗之类的，类别Label之间没有什么大小关系；\n",
    "* 排序问题：则介于回归问题和分类问题之间。Label是离散值，但不同档位的值有大小关系。\n",
    "    * 例子1：用户在搜索引擎里输入一个关键词，返回一堆结果，通常会按照满足程度，对这些结果分成0,1,2,3,4五档。 同分类问题做比较，把0档分成1档 和 把0档分成2档，这种错误程度明显是不同的。这些档位在一定的大小关系，排序的目标是尽可能把3档的满足的特别好的结果排在前面。\n",
    "    * 例子2：预测明天股票情况，只要能预测到明天涨幅可能最大的10只就可以，而不用关系其他几千个股票的情况。\n",
    "\n",
    "解决排序问题的三种思路：\n",
    "1. point-wise, 当成一个回归问题，预测每个结果的分值，预测得分和档位label均方误差作为损失函数，最终根据预测的分值排序；\n",
    "2. pair-wise, 同一组内的样本，两两构成一个pair(a,b)，如果a>b为正样本，如果a<b为负样本, 转换为一个二分类问题，a=b?\n",
    "3. list-wise，根据实际的排序情况和理想排序情况的diff，调整；\n",
    "\n",
    "* 数据集的构造方式\n",
    "* 微软rank数据集 \n",
    "\n",
    "## 排序问题的衡量指标：\n",
    "* 累计增益(CG) cumulative gain :\n",
    "* 折损累计增益(DCG) Discounted CG:\n",
    "* 归一化折损累计增益(NDCG) Normalized DCG:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "id": "62009c6f",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "dcg:13.848263629272981\n",
      "idcg:14.595390756454924\n",
      "ndcg:0.9488107485678985\n",
      "ndcg:0.6956940443813076\n",
      "ndcg2:0.9999999999999998\n",
      "\n"
     ]
    }
   ],
   "source": [
    "# 排序问题的衡量指标:cg,dcg,ndcg\n",
    "import math\n",
    "import numpy as np\n",
    "from sklearn.metrics import ndcg_score\n",
    "\n",
    "#假设有5个结果的分数分别是 3、2、3、0、1、2\n",
    "x = np.array([3,2,3,0,1,2])\n",
    "\n",
    "cg = x.sum()\n",
    "\n",
    "def dcg(scores):\n",
    "    \"\"\"\n",
    "    compute the DCG value based on the given score\n",
    "    :param scores: a score list of documents\n",
    "    :return v: DCG value\n",
    "    \"\"\"\n",
    "    v = 0\n",
    "    for i in range(len(scores)):\n",
    "        # val_i = scores[i]/math.log2(scores[i]+2)\n",
    "        # 增加相关度影响比重的DCG计算方式\n",
    "        v += (np.power(2, scores[i]) - 1) / np.log2(i+2)  # i+2 is because i starts from 0\n",
    "    return v\n",
    "\n",
    "def idcg(scores):\n",
    "    \"\"\"\n",
    "    compute the IDCG value (best dcg value) based on the given score\n",
    "    :param scores: a score list of documents\n",
    "    :return:  IDCG value\n",
    "    \"\"\"\n",
    "    best_scores = sorted(scores)[::-1]\n",
    "    return dcg(best_scores)\n",
    "\n",
    "def ndcg(scores):\n",
    "    \"\"\"\n",
    "    compute the NDCG value based on the given score\n",
    "    :param scores: a score list of documents\n",
    "    :return:  NDCG value\n",
    "    \"\"\"\n",
    "    return dcg(scores)/idcg(scores)\n",
    "\n",
    "def ndcg_k(scores, k):\n",
    "    scores_k = scores[:k]\n",
    "    dcg_k = dcg(scores_k)\n",
    "    idcg_k = dcg(sorted(scores)[::-1][:k])\n",
    "    if idcg_k == 0:\n",
    "        return np.nan\n",
    "    return dcg_k/idcg_k\n",
    "\n",
    "dcg_val = dcg(x)\n",
    "idcg_val = idcg(x)\n",
    "ndcg_val = ndcg(x)\n",
    "print(f\"dcg:{dcg_val}\")\n",
    "print(f\"idcg:{idcg_val}\")\n",
    "print(f\"ndcg:{ndcg_val}\")\n",
    "\n",
    "# 使用sklearn.metrics.ndcg_score\n",
    "# https://scikit-learn.org/stable/modules/generated/sklearn.metrics.ndcg_score.html\n",
    "true_relevance = np.asarray([[10, 0, 0, 1, 5]]) #真实的\n",
    "scores = np.asarray([[.1, .2, .3, 4, 70]]) #预测的\n",
    "\n",
    "ndcg = ndcg_score(true_relevance, scores)\n",
    "print(f\"ndcg:{ndcg}\")\n",
    "ndcg2 = ndcg_score(np.asarray([[3,3,2,2,1,0]]), np.asarray([[3,3,2,2,1,0]]))\n",
    "print(f\"ndcg2:{ndcg2}\\n\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6ea074f6",
   "metadata": {},
   "source": [
    "# 1. point-wise\n",
    "\n",
    "模型跟普通的回归问题一样"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "d6a00899",
   "metadata": {},
   "source": [
    "# 2. Pair-wise\n",
    "https://www.cnblogs.com/little-horse/p/10468311.html\n",
    "\n",
    "同一组内，两两构造一个pair对，训练模型时，输入是pair对的两个向量，输出是三种a>b label为1,a=b label为0 (这个需要吗？)，a<b, label为-1。 预测时，只使用ab比较前的网络。\n",
    "\n",
    "缺点：\n",
    "1. 样本数量将会增加很多倍 \n",
    "2. 对噪声标注更敏感，即一个错误标注会引起多个 pair 标注错误 \n",
    "3. 仅考虑了 pair 的相对位置，同样也没有考虑样本在预测排序中的位置信息"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "c589f50b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import torch\n",
    "import torch.nn as nn\n",
    "\n",
    "class RankNet(nn.Module):\n",
    "    def __init__(self, num_features,hidden=[512,256,128]):\n",
    "        # hidden 的数值为超参数，可通过Gridsearch确定一个合适值\n",
    "        super(RankNet, self).__init__()\n",
    "        self.model = nn.Sequential(\n",
    "            nn.Linear(num_features,hidden[0]), \n",
    "            nn.Dropout(0.2), \n",
    "            nn.ReLU(),\n",
    "            nn.Linear(hidden[0], hidden[1]), \n",
    "            nn.Dropout(0.2),\n",
    "            nn.ReLU(), \n",
    "            nn.Linear(hidden[1], hidden[2]),\n",
    "            nn.Dropout(0.2), \n",
    "            nn.ReLU(),\n",
    "            nn.Linear(hidden[2], 1))\n",
    "        self.sigmoid = nn.Sigmoid()\n",
    "\n",
    "    def forward(self, input1, input2):\n",
    "        # 训练过程中，接受pair对中的两个向量，通过model获取得分，两个得分差值过sigmoid函数，用于bce计算损失\n",
    "        s1 = self.model(input1)\n",
    "        s2 = self.model(input2)\n",
    "        diff = s1 - s2\n",
    "        prob = self.sigmoid(diff)\n",
    "        return prob\n",
    "\n",
    "    def predict(self, input_):\n",
    "        # 实际预测的时候，只需要输入一个，得到得分即可\n",
    "        return self.model(input_)\n",
    "\n",
    "model = RankNet(10)\n",
    "criterion = nn.BCELoss() #使用bce损失函数"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70f07956",
   "metadata": {},
   "source": [
    "# 2. List-wise\n",
    "LambdaRank, NDCG非凸且不可导, 损失函数或者梯度该怎么定义？\n",
    "\n",
    "* https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/MSR-TR-2010-82.pdf\n",
    "* https://papers.nips.cc/paper/2971-learning-to-rank-with-nonsmooth-cost-functions.pdf\n",
    "* https://github.com/haowei01/pytorch-examples/blob/master/ranking/LambdaRank.py\n",
    "* https://github.com/airalcorn2/RankNet/blob/master/lambdarank.py\n",
    "\n",
    "* https://github.com/houchenyu/L2R/blob/master/lambdaRank.py"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "7923ae5b",
   "metadata": {},
   "outputs": [],
   "source": [
    "class LambdaRankModule(nn.Module):\n",
    "    def __init__(self, num_features,hidden=[128,64,32]):\n",
    "        super(LambdaRankModule, self).__init__()\n",
    "        self.model = nn.Sequential(\n",
    "            nn.Linear(num_features,hidden[0]), \n",
    "            nn.Dropout(0.2), \n",
    "            nn.ReLU(),\n",
    "            nn.Linear(hidden[0], hidden[1]), \n",
    "            nn.Dropout(0.2),\n",
    "            nn.ReLU(), \n",
    "            nn.Linear(hidden[1], hidden[2]),\n",
    "            nn.Dropout(0.2), \n",
    "            nn.ReLU(),\n",
    "            nn.Linear(hidden[2], 1))\n",
    "        \n",
    "        \n",
    "    def forward(self, input1):\n",
    "        s1 = self.model(input1)\n",
    "        return s1 \n",
    "\n",
    "n_docs = 8\n",
    "n_rel = 5 #\n",
    "n_irr = n_docs - n_rel\n",
    "\n",
    "model = LambdaRankModule(10)\n",
    "docs = torch.rand(n_docs,10) #n_docs-batch,10-num_features\n",
    "# print(docs)\n",
    "doc_scores = model(docs)\n",
    "# print(doc_scores)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d8037cb",
   "metadata": {},
   "source": [
    "* LambdaRank是一个经验算法，不通过显示定义损失函数再求梯度的方式对排序问题进行求解，而是分析排序问题需要的梯度的意义，直接定义梯度。\n",
    "* Lambda量化了一个待排序的文档在下一次迭代时应该调整的方向和强度。\n",
    "* 通过交换每对文档后 NDCG 的变化来衡量梯度.\n",
    "* |ΔNDCG|是交换排序结果Ui和Uj得到的NDCG差值。NDCG倾向于将排名高并且相关性高的文档更快地向上推动，而排名地而且相关性较低的文档较慢地向上推动。\n",
    "* https://www.cnblogs.com/genyuan/p/9788294.html\n",
    "* 直接把 RankNet 最后得到的 Lambda 梯度拿来作为 LambdaRank 的梯度来用了？\n",
    "![test2](https://www.zhihu.com/equation?tex=++++%5Clambda_%7Bij%7D%5Cmathrel%7B%5Cstackrel%7B%5Cmbox%7Bdef%7D%7D%7B%3D%7D%7D+-+%5Cfrac%7B1%7D%7B1+%2B+%5Cexp%5Cbigl%28s_i+-+s_j%5Cbigr%29%7D+%5C%5C)\n",
    "![test](https://www.zhihu.com/equation?tex=++++%5Clambda_%7Bij%7D+%3D+-+%5Cfrac%7B1%7D%7B1+%2B+%5Cexp%5Cbigl%28s_i+-+s_j%5Cbigr%29%7D+%5Ccdot+%5Clvert%5CDelta+Z_%7Bij%7D%5Crvert+%5C%5C)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "68890856",
   "metadata": {},
   "outputs": [],
   "source": [
    "# def idcg(n_rel):\n",
    "#     # Assuming binary relevance. 这个假设有点奇怪\n",
    "#     nums = np.ones(n_rel)\n",
    "#     denoms = np.log2(np.arange(n_rel) + 1 + 1)\n",
    "#     return (nums / denoms).sum()\n",
    "\n",
    "def c_lambda():\n",
    "    # Document ranks.\n",
    "    (sorted_scores, sorted_idxs) = doc_scores.sort(dim=0, descending=True) #对预测得分从大到小排序\n",
    "    doc_ranks = torch.zeros(n_docs)\n",
    "    doc_ranks[sorted_idxs] = 1 + torch.arange(n_docs).view((n_docs, 1)).float()\n",
    "    doc_ranks = doc_ranks.view((n_docs, 1))\n",
    "\n",
    "    # Compute lambdas.\n",
    "    # See equation (6) in [2] and equation (9) in [1].\n",
    "    score_diffs = doc_scores[:n_rel] - doc_scores[n_rel:].view(n_irr)\n",
    "    # print(doc_scores[:n_rel])\n",
    "    # print(doc_scores[n_rel:].view(n_irr))\n",
    "    exped = score_diffs.exp()\n",
    "    N = 1 / idcg(n_rel)\n",
    "    dcg_diffs = 1 / (1 + doc_ranks[:n_rel]).log2() - (1 / (1 + doc_ranks[n_rel:]).log2()).view(n_irr)\n",
    "    lamb_updates = 1 / (1 + exped) * N * dcg_diffs.abs()\n",
    "    # print(lamb_updates)\n",
    "    lambs = torch.zeros((n_docs, 1))\n",
    "    lambs[:n_rel] += lamb_updates.sum(dim=1, keepdim=True)\n",
    "    lambs[n_rel:] -= lamb_updates.sum(dim=0, keepdim=True).t()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "id": "8ddf742d",
   "metadata": {},
   "outputs": [],
   "source": [
    "#https://github.com/houchenyu/L2R/blob/master/lambdaRank.py  \n",
    "def single_dcg(scores, i, j):\n",
    "    \"\"\"\n",
    "    compute the single dcg that i-th element located j-th position\n",
    "    :param scores:\n",
    "    :param i:\n",
    "    :param j:\n",
    "    :return:\n",
    "    \"\"\"\n",
    "    return (np.power(2, scores[i]) - 1) / np.log2(j+2)\n",
    "\n",
    "def compute_lambda(true_scores, predict_scores, order_pairs, qid):\n",
    "    \"\"\"\n",
    "    :param true_scores: the score list of the documents for the qid query\n",
    "    :param predict_scores: the predict score list of the these documents\n",
    "    :param order_pairs: the partial oder pairs where first document has higher score than the second one\n",
    "    :param qid: specific query id\n",
    "    :return:\n",
    "        lambdas: changed lambda value for these documents\n",
    "        w: w value\n",
    "        qid: query id\n",
    "    \"\"\"\n",
    "    doc_num = len(true_scores)\n",
    "    lambdas = np.zeros(doc_num)\n",
    "    w = np.zeros(doc_num)\n",
    "    IDCG = idcg(true_scores)\n",
    "    single_dcgs ={}\n",
    "    for i, j in order_pairs:\n",
    "        if (i, i) not in single_dcgs:\n",
    "            single_dcgs[(i, i)] = single_dcg(true_scores, i, i)\n",
    "        if (j, j) not in single_dcgs:\n",
    "            single_dcgs[(j, j)] = single_dcg(true_scores, j, j)\n",
    "        single_dcgs[(i, j)] = single_dcg(true_scores, i, j)\n",
    "        single_dcgs[(j, i)] = single_dcg(true_scores, j, i)\n",
    "\n",
    "    for i, j in order_pairs:\n",
    "        delta = abs(single_dcgs[(i,j)] + single_dcgs[(j,i)] - single_dcgs[(i,i)] -single_dcgs[(j,j)])/IDCG\n",
    "        rho = 1 / (1 + np.exp(predict_scores[i] - predict_scores[j]))\n",
    "        lambdas[i] += rho * delta\n",
    "        lambdas[j] -= rho * delta\n",
    "\n",
    "        rho_complement = 1.0 - rho\n",
    "        w[i] += rho * rho_complement * delta\n",
    "        w[j] -= rho * rho_complement * delta\n",
    "\n",
    "    return lambdas, w, qid"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "d6bfd5ec",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
